﻿module Heap
///p73 算法导论

            
open System

//查找父子兄弟节点的函数用内联形式编写
//实现heap {} 计算表达式
//类型要是 'a heap 
//这样才好用

///这些计算结果没有保证有效
///需要自己判断保证
let  inline  private parent i  =i>>>1
let inline private left i  = i<<<1
let inline private right i =(i<<<1)+1
let  exchange (arr:int []) a b =
    let t = arr.[a]
    arr.[a]<-arr.[b]
    arr.[b]<-t

///O(lgn) n是数组元素
let  rec   Heapify (arr:int [],heapSize)  i  (cmp:int32[]->int32->int32->int32)=
    let l =left i
    let r =right i
    let mutable select = i
    if l <= heapSize  then
        select<- cmp arr i l
    if r <= heapSize then
        select<- cmp arr select r
    if select <> i then
        exchange arr select i
        Heapify (arr,heapSize) select  cmp

///O(n) n是数组元素
let BuildHeap(A:int32 [] , heapSize) ( heapify: int[]*int32->int32->unit) =
    let rec loop  c =
        if c = 0 then ()
        else 
            heapify (A,heapSize) c 
            loop (c-1)
    loop <| heapSize/2

///O(nlgn)
let Sort(A:int32[],heapSize:int32 ref) heapify=
    BuildHeap  (A,!heapSize) heapify
    let rec loop i =
        if i =1 then ()
        else
            exchange A 1 i
            decr  heapSize 
            heapify (A,!heapSize) 1
            loop (i-1)
    loop !heapSize


